'''
Created on Apr 28, 2011

@author: user
'''


#array = [3, 4, 9, 14, 15, 19, 28, 37, 47, 50]
array = [1,2,3,4,6]
canBeMadeByLower = {}

def canMake(x):
    if canBeMadeByLower.has_key(x):
        return True
    else:
        return False

def getPos(x):
    if x in array:
        return array.index(x)
    
    for i in range(1,len(array)):
        if array[i] > x:
            return i  

def initialPop():
    highest = array[len(array)-1]
    print highest
         
    for i in range(highest):
        print "GetPos", i, getPos(i)
        for j in reversed(range(0,getPos(i))):
            if i - array[j] > array[j]:
                continue
            if canMake(i-array[j]):
                if canBeMadeByLower.has_key(i) == False:
                    canBeMadeByLower[i] = 1
                else:
                    canBeMadeByLower[i] = canBeMadeByLower[i]+1
                print i, array[j]
            else:
                if ((i - array[j]) in array): 
                    if (i-array[j]) != array[j]:
                        if canBeMadeByLower.has_key(i) == False:
                            canBeMadeByLower[i] = 1
                        else:
                            canBeMadeByLower[i] = canBeMadeByLower[i]+1
                        print i, array[j]
                        
    
    print canBeMadeByLower
 
def countSubSet():
    count = 0
    length = len(array)

    
    initialPop()
    
    for i in range(length):
        for j in reversed(range(i)):
            if array[i] - array[j] > array[j]:
                continue
            if canMake(array[i] - array[j]):
                if canBeMadeByLower.has_key(array[i]) == False:
                    canBeMadeByLower[array[i]] = 1
                
                print array[i], array[j], array[i]-array[j] , canBeMadeByLower[array[i]-array[j]]
                count = count + canBeMadeByLower[array[i]-array[j]]
            
            if ((array[i] - array[j]) in array): 
                if (array[i] - array[j]) != array[j]:
                    if canBeMadeByLower.has_key(array[i]) == False:
                        canBeMadeByLower[array[i]] = 1
                        
                    print array[i], array[j], array[i]-array[j] 
                    if canBeMadeByLower.has_key(array[i]-array[j]):
                        count = count + canBeMadeByLower[array[i]-array[j]]
                    else:
                        count = count+1
        print canBeMadeByLower
    print count

if __name__ == '__main__':
    countSubSet()
    #initialPop()
   
    